//
// Created by wangxiyue on 2019/8/16.
//

#include <stdio.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int minimumTotal(int **triangle, int triangleSize, int *triangleColSize) {

    int s[triangleSize][*triangleColSize];
    s[0][0] = triangle[0][0];
    int minValue = 0;
    for (int i = 1; i < triangleSize; ++i) {
        for (int j = 0; j < *triangleColSize; ++j) {
            if (j == 0) {
                s[i][j] = s[i - 1][j] + triangle[i][j];
            } else if (j == *triangleColSize - 1) {
                s[i][j] = s[i - 1][j - 1] + triangle[i][j];
            } else {
                s[i][j] = min(s[i - 1][j], s[i - 1][j - 1]) + triangle[i][j];
            }
            if (i == triangleSize - 1) {
                if (j == 0) {
                    minValue = s[i][j];
                } else {
                    minValue = min(minValue, s[i][j]);
                }
            }
        }
    }
    return minValue;
}

int main() {

    int triangle[4][4] = {{2},
                          {3, 4},
                          {6, 5, 7},
                          {4, 1, 8, 3}};

    int triangleColSize = 4;
    int a = minimumTotal(triangle, 4, &triangleColSize);
    printf("%d\n",a);
    return 0;
}